package lpg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

class Base
{
    //
    // Constructor
    //
    Base(Control control)
    {
        this.control    = control;
        this.option     = control.option;
        this.lexStream  = control.lexStream;
        this.grammar    = control.grammar;

        output = new BaseOutput(control, this);
    }

    //
    // MKFIRST constructs the FIRST and FOLLOW maps, the CLOSURE map,
    // ADEQUATE_ITEM and itemTable maps and all other basic maps.
    //
    void processBasicMaps()
    {
        //
        // NT_FIRST is used to construct a mapping from non-terminals to the
        // set of terminals that may appear first in a string derived from
        // the non-terminal.
        //
        ntFirst = new BoundedArray<BitSet>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
            ntFirst.set(i, new BitSet(grammar.numTerminals + 1));

        //
        // Check if there are any non-terminals that do not produce
        // any rules.
        //
        noRulesProduced();

        //
        // Construct the CLOSURE map of non-terminals.
        //
        closure = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
            closure.set(i, new IntArrayList());
        indexOf = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        indexOf.fill(Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            if (indexOf.get(nt) == Util.OMEGA)
                computeClosure(nt);

        generatesNull = new BoundedBooleanArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        indexOf.fill(Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            if (indexOf.get(nt) == Util.OMEGA)
                checkCanGenerateNull(nt);

        //
        // Construct the FIRST map for non-terminals and also a list
        // of non-terminals whose first set is empty.
        //
        indexOf.fill(Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            if (indexOf.get(nt) == Util.OMEGA)
                computeFirst(nt);

        //
        //  Since every input source will be followed by the EOFT
        //  symbol, FIRST[accept_image] cannot contain empty but
        //  instead must contain the EOFT symbol.
        //
        if (generatesNull.get(grammar.acceptImage))
        {
            generatesNull.set(grammar.acceptImage, false);
            ntFirst.get(grammar.acceptImage).clear(grammar.empty);
            ntFirst.get(grammar.acceptImage).set(grammar.eofImage);
        }

        //
        // Construct the itemTable, firstItemOf, and ntItems maps.
        //
        itemTable = new Itemtab[grammar.numItems + 1];
        firstItemOf = new int[grammar.numRules + 1];
        nextItem = new int[grammar.numItems + 1];
        ntItems = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        ntItems.fill(Util.NIL);
        firstTable = new int[grammar.numSymbols + 1];
        Arrays.fill(firstTable, Util.NIL);

        assert (first.isEmpty());
        first.add(null); // skip zeroth element

        int firstOfEmpty = first.size(); // use 1st slot for empty
        first.add(new FirstElementType(1, 0));

        int itemNo = 0;
        itemTable[itemNo] = new Itemtab(0, grammar.empty, 0, Util.NIL);

        for (int ruleNo = grammar.firstRule(); ruleNo <= grammar.lastRule(); ruleNo++)
        {
            firstItemOf[ruleNo] = itemNo + 1;
            int j = 0;
            int k = grammar.rules.get(ruleNo + 1).rhsIndex - 1;
            for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo); i++)
            {
                itemNo++;
                int symbol = grammar.rhsSym.get(i);

                int suffixIndex = Util.NIL;
                if (option.lalrLevel > 1 ||
                    grammar.isNonTerminal(symbol) ||
                    symbol == grammar.errorImage)
                {
                    suffixIndex = (i == k) ? firstOfEmpty : firstMap(i + 1, k);
                }
                itemTable[itemNo] = new Itemtab(ruleNo, symbol, j, suffixIndex);

                if (grammar.isNonTerminal(symbol))
                {
                    nextItem[itemNo] = ntItems.get(symbol);
                    ntItems.set(symbol, itemNo);
                }
                j++;
            }

            itemTable[++itemNo] = new Itemtab(ruleNo, grammar.empty, j, Util.NIL);
        }

        //
        // We now compute the first set for all suffixes that were
        // inserted in the FIRST map.
        // Extra space is also allocated to compute the first set for
        // suffixes whose left-hand side is the ACCEPT non-terminal.
        // The first set for these suffixes are the sets needed to
        // construct the FOLLOW map and compute look-ahead sets.  They
        // are placed in the FIRST table in the range 1..NUM_FIRST_SETS
        // The first element in the FIRST table contains the first sets
        // for the empty sequence.
        //
        for (int i = 1, n = first.size(); i < n; i++)
        {
            first.get(i).set = new BitSet(grammar.numTerminals + 1);
            suffixFirst(i);
        }

        //
        // There must be only one rule whose left-hand side is accep_image.
        //
        int index = first.size();
        itemNo = firstItemOf[grammar.rulesOfLhs(grammar.acceptImage).get(0)];
        itemTable[itemNo].suffixIndex = index;
        FirstElementType firstElem = new FirstElementType();
        firstElem.set = new BitSet(grammar.numTerminals + 1);
        firstElem.set.set(grammar.eofImage);
        first.add(firstElem);

        //
        // If the READ/REDUCE option is on, we precalculate the kernel
        // of the final states which simply consists of the last item
        // in  the corresponding rule.  Rules with the ACCEPT
        // non-terminal as their left-hand side are not considered so
        // as to let the Accpet action remain as a Reduce action
        // instead of a Goto/Reduce action.
        //
        if (option.readReduce)
        {
            adequateItem = new Node[grammar.numRules + 1];
            for (int ruleNo = grammar.firstRule(); ruleNo <= grammar.lastRule(); ruleNo++)
            {
                int rhsSize = grammar.rhsSize(ruleNo);
                if (grammar.rules.get(ruleNo).lhs != grammar.acceptImage)
                {
                    itemNo = firstItemOf[ruleNo] + rhsSize;
                    adequateItem[ruleNo] = new Node(itemNo, null);
                }
            }
        }

        //
        // Construct the CLITEMS map. Each element of CLITEMS points
        // to a circular linked list of items.
        //
        clitems = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            IntArrayList clitemsList = new IntArrayList();
            clitems.set(nt, clitemsList);
            IntArrayList rules = grammar.rulesOfLhs(nt);
            for (int i = 0, n = rules.size(); i < n; i++)
                clitemsList.add(firstItemOf[rules.get(i)]);
        }

        //
        // Construct the GENERATES_STRING map for non-terminals.
        //
        IntArrayList badList = new IntArrayList();
        IntArrayList dependList = new IntArrayList();
        generatesString = new BoundedBooleanArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        isCyclic = new BoundedBooleanArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        indexOf.fill(Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            if (indexOf.get(nt) == Util.OMEGA)
                checkCanGenerateString(nt);
            if (!generatesString.get(nt))
                if (isCyclic.get(nt))
                    badList.add(nt);
                else
                    dependList.add(nt);
        }

        if (!badList.isEmpty() || !dependList.isEmpty())
        {
            StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
            for (int i = 0, n = badList.size(); i < n; i++)
            {
                int symbol = badList.get(i);
                grammar.restoreSymbol(tok, grammar.retrieveString(symbol));

                option.emitError(grammar.retrieveTokenLocation(symbol),
                        "The nonterminal " + tok + " cannot generate complete strings of terminals");
            }
            control.exit();
        }

        //
        // Compute the STRING_GENERATED and PROSTHESIS_RULE maps, if needed.
        //
        if (option.errorMaps)
        {
            stringGenerated = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
                stringGenerated.set(i, new IntArrayList());

            prosthesisRule = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            indexOf.fill(Util.OMEGA);
            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                if (indexOf.get(nt) == Util.OMEGA)
                    computeStringGeneration(nt);
            }
        }

        //
        // If LALR_LEVEL > 1, we need to calculate RMPSELF, a set that
        // identifies the nonterminals that can right-most produce
        // themselves. In order to compute RMPSELF, the map PRODUCES
        // must be constructed which identifies for each nonterminal
        // the set of nonterminals that it can right-most produce.
        //
        if (option.lalrLevel > 1)
        {
            directProduces = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            produces = new BoundedArray<BitSetWithOffset>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                directProduces.set(nt, new IntArrayList());
                produces.set(nt, new BitSetWithOffset(grammar.numNonterminals + 1, grammar.numTerminals));
            }

            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                IntArrayList clitemsList = clitems.get(nt);
                for (int k = 0, m = clitemsList.size(); k < m; k++)
                {
                    itemNo = clitemsList.get(k);
                    int symbol = itemTable[itemNo].symbol;
                    if (grammar.isNonTerminal(symbol))
                    {
                        int i = itemTable[itemNo].suffixIndex;
                        if (first.get(i).set.get(grammar.empty) && !produces.get(nt).get(symbol))
                        {
                            produces.get(nt).set(symbol);
                            directProduces.get(nt).add(symbol);
                        }
                    }
                }
            }

            //
            // Complete the construction of the RIGHT_MOST_PRODUCES map
            // for non-terminals using the digraph algorithm.
            //
            indexOf.fill(Util.OMEGA);
            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
                if (indexOf.get(nt) == Util.OMEGA)
                    computeProduces(nt);

            initRmpself(produces);
        }

        //
        // Construct the FOLLOW map if
        //   1) an SLR table is requested
        //   2) if we have to print the FOLLOW map
        //   3) Error-maps are requested
        //   4) There are more than one starting symbol.
        //
        if (option.slr || option.follow || option.errorMaps ||
                grammar.rulesOfLhs(grammar.acceptImage).size() > 1)
        {
            follow = new BoundedArray<BitSet>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
                follow.set(i, new BitSet(grammar.numTerminals + 1));
            follow.get(grammar.acceptImage).set(grammar.eofImage);

            indexOf.fill(Util.OMEGA);
            indexOf.set(grammar.acceptImage, Util.INFINITY);  // mark computed
            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                if (indexOf.get(nt) == Util.OMEGA) // not yet computed ?
                    computeFollow(nt);
            }

            //
            // Initialize FIRST for suffixes that can follow each starting
            // non-terminal (except the main symbol) with the FOLLOW set
            // of the non-terminal in question.
            //
            if (grammar.rulesOfLhs(grammar.acceptImage).size() > 1)
            {
                int ruleNo = grammar.rulesOfLhs(grammar.acceptImage).get(0);
                int top = itemTable[firstItemOf[ruleNo]].suffixIndex;
                for (int i = top + 1, k = 0, n = first.size(); i < n; i++, k++)
                {
                    ruleNo = grammar.rulesOfLhs(grammar.acceptImage).get(k);
                    itemNo = firstItemOf[ruleNo];
                    int symbol = itemTable[itemNo].symbol;
                    if (grammar.isNonTerminal(symbol))
                        first.get(i).set = (BitSet)follow.get(symbol).clone();
                }
            }
        }

        //
        // If we are constructing a backtracking parser, we need to order
        // the rules based on the relation:
        //
        //    (A, B) is in the relation iff A ::=* B xxx
        //
        // Note that this implies that (A, B) if A ::= yyy B xxx if
        // yyy =>* empty.
        //
        if (option.backtrack)
        {
            rank = new int[grammar.numRules + 1];

            lhsRankedRules = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
            for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
                lhsRankedRules.set(i, new IntArrayList());

            //
            // In this loop, we construct the lhsRankedRules map which maps
            // each non-terminal symbol into the set of rules it produces.
            // When we encounter a rule where the priority is explicitly set,
            // we process it right away.
            //
            for (int ruleNo = grammar.firstRule(); ruleNo <= grammar.lastRule(); ruleNo++)
            {
                if (option.priority && grammar.rules.get(ruleNo).isPriorityProduction())
                    orderedRules.add(ruleNo);
                else
                {
                    int symbol = grammar.rules.get(ruleNo).lhs;
                    lhsRankedRules.get(symbol).add(ruleNo);
                }
            }

            //
            // Now assign priorities to rules based on partial order of the
            // nonterminals (left-hand sides). See ComputeRank for the
            // relation on which the partial order is constructed.
            //
            indexOf.fill(Util.OMEGA);
            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                if (indexOf.get(nt) == Util.OMEGA)
                    computeRank(nt);
            }

            for (int i = 0, n = orderedRules.size(); i < n; i++)
                rank[orderedRules.get(i)] = i + 1;
            lhsRankedRules = null; // free space

            //
            // Report any problem found in computing the rank of the rules.
            //
            if (option.priority)
            {
                //
                // First, flush any data left in the report buffer.
                //
                option.flushReport();

                output.printRank(sccInRanks, orderedRules, rank);
            }

            sccInRanks.clear(); // free space
        }

        //
        // Construct the LAST map from each non-terminal A into a set
        // of terminals that may appear as the last symbol in a string
        // derived from A. I.e., if (A =>* X t) where X is an arbitrary
        // string then t is in LAST(A).
        //
        if (!grammar.checkPredecessorSetsFor.isEmpty())
        {
            last = new BitSet[grammar.numSymbols + 1];
            last[0] = new BitSet(grammar.numTerminals + 1);
            indexOf = new BoundedIntArray(0, last.length);
            indexOf.set(0, Util.INFINITY);
            for (int i = 1, n = last.length; i < n; i++)
            {
                last[i] = new BitSet(grammar.numTerminals + 1);
                if (grammar.isTerminal(i))
                {
                    last[i].set(i);
                    indexOf.set(i, Util.INFINITY);
                }
                else
                    indexOf.set(i, Util.OMEGA);
            }

            for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            {
                if (indexOf.get(nt) == Util.OMEGA)
                    computeLast(nt);
            }

            itemOf = new IntArrayList[grammar.numSymbols + 1];
            for (int i = 0; i < itemOf.length; i++)
                itemOf[i] = new IntArrayList();
            for (itemNo = 0; itemNo < itemTable.length; itemNo++)
            {
                int symbol = itemTable[itemNo].symbol;
                itemOf[symbol].add(itemNo);
            }

            predecessor = new BitSet[grammar.numSymbols + 1];
            for (int i = 0; i < predecessor.length; i++)
                predecessor[i] = new BitSet(grammar.numTerminals + 1);

            indexOf = new BoundedIntArray(0, predecessor.length);
            indexOf.fill(Util.OMEGA);
            for (int i = grammar.firstTerminal(); i <= grammar.lastNonTerminal(); i++)
                if (indexOf.get(i) == Util.OMEGA)
                    computePredecessor(i);

            //
            // Check the predecessor sets of each pairs of symbols.
            // If their intersection is not empty then issue an error message.
            //
            for (int i = 0, n = grammar.checkPredecessorSetsFor.size(); i < n; i++)
            {
                int leftSymbol = grammar.checkPredecessorSetsFor.get(i).leftSymbol;
                int rightSymbol = grammar.checkPredecessorSetsFor.get(i).rightSymbol;
                BitSet inter = (BitSet)predecessor[leftSymbol].clone();
                inter.and(predecessor[rightSymbol]);
                StringBuilder leftTok = new StringBuilder(Control.SYMBOL_SIZE);
                StringBuilder rightTok = new StringBuilder(Control.SYMBOL_SIZE);
                for (int k = inter.nextSetBit(0); k >= 0; k = inter.nextSetBit(k + 1))
                {
                    grammar.restoreSymbol(leftTok, grammar.retrieveString(leftSymbol));
                    grammar.restoreSymbol(rightTok, grammar.retrieveString(rightSymbol));

                    option.emitError(grammar.retrieveTokenLocation(k),
                            "This symbol is a predecessor of both \"" +
                            leftTok + "\"  and \"" + rightTok + "\"");
                }
            }
        }

        //
        // If WARNINGS option is turned on, the unreachable symbols in
        // the grammar and duplicate rules are reported.
        //
        if (option.warnings)
        {
            checkDuplicateRules();
            printUnreachables();
        }

        option.flushReport();
    }

    //
    // DEPRECATED: TODO: Note that since the new input format does
    // not require terminal symbols to be declared, all non-declared
    // grammar symbols are assumed to be terminals. Therefore, it
    // will never be the case that we detect a nonterminal that does not
    // produce any rule.
    //
    private void noRulesProduced()
    {
        //
        // Build a list of all non-terminals that do not produce any
        // rules.
        //
        IntArrayList list = new IntArrayList();
        for (int symbol = grammar.firstNonTerminal(); symbol <= grammar.lastNonTerminal(); symbol++)
        {
            if (grammar.rulesOfLhs(symbol).isEmpty())
                list.add(symbol);
        }

        //
        // If the list of non-terminals that do not produce any rules
        // is not empty, signal error and stop.
        //
        if (!list.isEmpty())
        {
            StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
            for (int i = 0, n = list.size(); i < n; i++)
            {
                int symbol = list.get(i);
                grammar.restoreSymbol(tok, grammar.retrieveString(symbol));

                option.emitError(grammar.retrieveTokenLocation(symbol),
                        "The nonterminal " + tok + " does not produce any rule.");
            }

            control.exit();
        }
    }

    //
    //  This function computes the closure of a non-terminal lhsSymbol passed
    // to it as an argument using the digraph algorithm.
    // The closure of a non-terminal A is the set of all non-terminals Bi that
    // can directly or indirectly start a string generated by A.
    // I.e., A *::= Bi X where X is an arbitrary string.
    //
    private void computeClosure(int lhsSymbol)
    {
        BoundedIntArray nontList = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        nontList.fill(Util.OMEGA);
        nontList.set(lhsSymbol, Util.NIL);
        int ntRoot = lhsSymbol;

        stack.add(lhsSymbol);
        int indx = stack.size();
        indexOf.set(lhsSymbol, indx);

        IntArrayList closureForLhsSymbol = closure.get(lhsSymbol);
        assert (closureForLhsSymbol.isEmpty());

        IntArrayList rules = grammar.rulesOfLhs(lhsSymbol);
        for (int i = 0, n = rules.size(); i < n; i++)
        {
            int ruleNo = rules.get(i);
            int symbol = (grammar.rhsSize(ruleNo) == 0
                                   ? grammar.empty
                                   : grammar.rhsSym.get(grammar.rules.get(ruleNo).rhsIndex));

            if (grammar.isNonTerminal(symbol))
            {
                if (nontList.get(symbol) == Util.OMEGA)
                {
                    if (indexOf.get(symbol) == Util.OMEGA) // if first time seen
                        computeClosure(symbol);

                    indexOf.set(lhsSymbol, Math.min(indexOf.get(lhsSymbol), indexOf.get(symbol)));
                    nontList.set(symbol, ntRoot);
                    ntRoot = symbol;

                    //
                    // add closure[symbol] to closure of lhsSymbol.
                    //
                    IntArrayList closureForSymbol = closure.get(symbol);
                    for (int k = 0, m = closureForSymbol.size(); k < m; k++)
                    {
                        int element = closureForSymbol.get(k);
                        if (nontList.get(element) == Util.OMEGA)
                        {
                            nontList.set(element, ntRoot);
                            ntRoot = element;
                        }
                    }
                }
            }
        }

        assert (closureForLhsSymbol.isEmpty());

        for (; ntRoot != lhsSymbol; ntRoot = nontList.get(ntRoot))
            closureForLhsSymbol.add(ntRoot);

        if (indexOf.get(lhsSymbol) == indx)
        {
            int top = stack.size() - 1;
            for (int symbol = stack.remove(top); symbol != lhsSymbol; symbol = stack.remove(--top))
            {
                IntArrayList closureForSymbol = closure.get(symbol);
                closureForSymbol.add(lhsSymbol);

                for (int k = 0, m = closureForLhsSymbol.size(); k < m; k++)
                {
                    int element = closureForLhsSymbol.get(k);
                    if (element != symbol)
                        closureForSymbol.add(element);
                }
                indexOf.set(symbol, Util.INFINITY);
            }
            indexOf.set(lhsSymbol, Util.INFINITY);
        }
    }

    //
    // This subroutine computes FIRST(NT) for some non-terminal NT using the
    // digraph algorithm.
    // FIRST(NT) is the set of all terminals Ti that may start a string generated
    // by NT. That is, NT *::= Ti X where X is an arbitrary string.
    //
    private void computeFirst(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);

        //
        // Iterate over all rules generated by non-terminal NT...
        // In this application of the transitive closure algorithm,
        //
        //  G(A) := { t | A ::= t X for a terminal t and a string X }
        //
        // The relation R is defined as follows:
        //
        //    R(A, B) iff A ::= B1 B2 ... Bk B X
        //
        // where Bi is nullable for 1 <= i <= k
        //
        IntArrayList rules = grammar.rulesOfLhs(nt);
        for (int k = 0, m = rules.size(); k < m; k++)
        {
            int ruleNo = rules.get(k);

            boolean blocked = false;
            for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo); i++)
            {
                int symbol = grammar.rhsSym.get(i);
                if (grammar.isNonTerminal(symbol))
                {
                    if (indexOf.get(symbol) == Util.OMEGA)
                        computeFirst(symbol);
                    indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));

                    BitSet tempSet = (BitSet)ntFirst.get(symbol).clone();
                    tempSet.clear(grammar.empty);
                    ntFirst.get(nt).or(tempSet);
                    blocked = !isNullable(symbol);
                }
                else
                {
                    ntFirst.get(nt).set(symbol);
                    blocked = true;
                }

                if (blocked)
                    break;
            }

            if (!blocked)
            {
                ntFirst.get(nt).set(grammar.empty);
            }
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            for (int symbol = stack.remove(top); symbol != nt; symbol = stack.remove(--top))
            {
                ntFirst.set(symbol, (BitSet)ntFirst.get(nt).clone());
                indexOf.set(symbol, Util.INFINITY);
            }
            indexOf.set(nt, Util.INFINITY);
        }
    }

    //
    // This subroutine computes LAST(NT) for some non-terminal NT using the
    // digraph algorithm.
    // LAST(NT) is the set of all terminals Ti that may appear last in a string
    // generated by NT. That is, NT *::= X Ti where X is an arbitrary string.
    //
    private void computeLast(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);

        IntArrayList clitemsList = clitems.get(nt);
        for (int k = 0, m = clitemsList.size(); k < m; k++)
        {
            int itemNo = clitemsList.get(k);
            int ruleNo = itemTable[itemNo].ruleNumber;
            int lastItemNo = itemNo + grammar.rhsSize(ruleNo) - 1;
            int i = lastItemNo;
            for (; i >= itemNo; i--)
            {
                int symbol = itemTable[i].symbol;
                if (grammar.isNonTerminal(symbol))
                {
                    if (indexOf.get(symbol) == Util.OMEGA)
                        computeLast(symbol);
                }
                indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));
                last[nt].or(last[itemTable[i].symbol]);
                if (grammar.isTerminal(symbol) || !isNullable(symbol))
                    break;
            }

            if (i < itemNo)
                last[nt].set(grammar.empty);
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            for (int symbol = stack.remove(top); symbol != nt; symbol = stack.remove(--top))
            {
                last[symbol] = (BitSet)last[nt].clone();
                indexOf.set(symbol, Util.INFINITY);
            }
            indexOf.set(nt, Util.INFINITY);
        }
    }

    //
    // This subroutine computes PREDECESSOR(x) for some symbol x using the
    // digraph algorithm.
    // PREDECESSOR(x) is the set of all terminals Ti that may immediately
    // prior to x.
    //
    private void computePredecessor(int symbol)
    {
        stack.add(symbol);
        int indx = stack.size();
        indexOf.set(symbol, indx);

        for (int k = 0, m = itemOf[symbol].size(); k < m; k++)
        {
            int itemNo = itemOf[symbol].get(k);
            for (; itemTable[itemNo].dot > 0; itemNo--)
            {
                int precedingSymbol = itemTable[itemNo - 1].symbol; // symbol before the dot
                predecessor[symbol].or(last[precedingSymbol]);
                if (!last[precedingSymbol].get(grammar.empty)) // is empty contained in the last set of symbol?
                    break;
            }

            if (itemTable[itemNo].dot == 0)
            {
                int ruleNo = itemTable[itemNo].ruleNumber;
                int lhsSymbol = grammar.rules.get(ruleNo).lhs;
                if (indexOf.get(lhsSymbol) == Util.OMEGA)
                    computePredecessor(lhsSymbol);
                indexOf.set(symbol, Math.min(indexOf.get(symbol), indexOf.get(lhsSymbol)));
                predecessor[symbol].or(predecessor[lhsSymbol]);
            }
        }

        if (indexOf.get(symbol) == indx)
        {
            predecessor[symbol].clear(grammar.empty);
            int top = stack.size() - 1;
            for (int other = stack.remove(top); other != symbol; other = stack.remove(--top))
            {
                predecessor[other] = (BitSet)predecessor[symbol].clone();
                indexOf.set(other, Util.INFINITY);
            }
            indexOf.set(symbol, Util.INFINITY);
        }
    }

    //
    // This subroutine computes GENERATES_STRING(x) for some nonterminal x using the
    // digraph algorithm.
    // GENERATES_STRING(x) is a boolean indicating whether or not x can generate
    // a string of terminals or the empty string.
    //
    private void checkCanGenerateString(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);
        generatesString.set(nt, false);
        isCyclic.set(nt, false);

        //
        // A non-terminal "A" can generate a terminal string if the grammar in
        // question contains a rule of the form:
        //
        //         A ::= X1 X2 ... Xn           n >= 0,  1 <= i <= n
        //
        // and Xi, for all i, is either a terminal or a non-terminal that can
        // generate a string of terminals.
        //
        IntArrayList rules = grammar.rulesOfLhs(nt);
        IntArrayList clitemsList = clitems.get(nt);
        for (int k = 0, m = clitemsList.size(); k < m && !generatesString.get(nt); k++)
        {
            int ruleNo = rules.get(k);
            boolean ruleGeneratesString = true; // assume this is true and see if we can prove it!
            for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo) && ruleGeneratesString; i++)
            {
                int symbol = grammar.rhsSym.get(i);
                if (grammar.isNonTerminal(symbol))
                {
                    if (indexOf.get(symbol) == Util.OMEGA)
                        checkCanGenerateString(symbol);
                    else
                        isCyclic.set(nt, isCyclic.get(nt) || symbol == nt); // a trivial cycle? record it!
                    indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));
                    ruleGeneratesString = generatesString.get(symbol);
                }
            }

            generatesString.set(nt, ruleGeneratesString);
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            int symbol = stack.remove(top);
            isCyclic.set(nt, isCyclic.get(nt) || symbol != nt); // more than one symbol in SCC?
            indexOf.set(nt, Util.INFINITY);
            for (; symbol != nt; symbol = stack.remove(--top))
            {
                generatesString.set(symbol, generatesString.get(nt));
                isCyclic.set(symbol, isCyclic.get(nt)); // obviously true!!!
                indexOf.set(symbol, Util.INFINITY);
            }
        }
    }

    //
    // This subroutine computes string_generated(x) for some nonterminal x using a
    // variant of the digraph algorithm.
    // string_generated(x) is a (possibly empty) string of terminals that can be
    // derived from x.
    //
    private void computeStringGeneration(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);
        stringGenerated.get(nt).clear();

        //
        // Keep track of whether or not a successful string was computed for the nonterminal nt.
        // If so, we will declare victory for nt. This is the way in which this algorithm differs
        // from the Digraph algorithm.
        //
        boolean successful = generatesNull.get(nt);

        //
        // If a nonterminal is nullable, we chose the NULL string as an examplar for it.
        //
        prosthesisRule.set(nt, 0); // for nullable nonterminal, this does not matter.
        if (!successful)
        {
            IntArrayList chosenRhs = new IntArrayList();
            IntArrayList tempRhs = new IntArrayList();
            //
            // Look at each rule generated by the nonterminal, simulate a parse through them
            // and pick the shortest string.
            //
            IntArrayList rules = grammar.rulesOfLhs(nt);
            for (int k = 0, m = rules.size(); k < m; k++)
            {
                tempRhs.clear();
                int ruleNo = rules.get(k);
                int i = grammar.firstRhsIndex(ruleNo);
                for (; i < grammar.endRhsIndex(ruleNo); i++)
                {
                    int symbol = grammar.rhsSym.get(i);
                    if (grammar.isTerminal(symbol))
                        tempRhs.add(symbol);
                    else if (!generatesNull.get(symbol))
                    {
                        if (indexOf.get(symbol) == Util.OMEGA)
                            computeStringGeneration(symbol);
                        indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));

                        //
                        // If symbol was successfully processed add its generated string
                        // to the list being constructed for ruleNo. Otherwise, move to the
                        // next rule associated with nt, if any.
                        //
                        if (indexOf.get(symbol) == Util.INFINITY &&
                            (stringGenerated.get(symbol).size() != 1 ||
                             stringGenerated.get(symbol).get(0) != Util.OMEGA))
                        {
                            IntArrayList listForSymbol = stringGenerated.get(symbol);
                            for (int j = 0, n = listForSymbol.size(); j < n; j++)
                                tempRhs.add(listForSymbol.get(j));
                        }
                        else
                            break;
                    }
                }
                if (i < grammar.endRhsIndex(ruleNo)) // not at end of rule?
                    continue;
                if (chosenRhs.isEmpty() || tempRhs.size() < chosenRhs.size())
                {
                    successful = true; // at least one string was found
                    prosthesisRule.set(nt, ruleNo);

                    chosenRhs.clear();
                    chosenRhs.addAll(tempRhs);
                    if (chosenRhs.size() == 1) // we're done!
                        break;
                }
            }

            //
            // TODO: Hash the info in chosen_rhs and have string generated point to the hashed element.
            //       StringGenerated should be an array of indices into a null-terminated string.
            //       I.e., a base array that is indexable by nonterminals; each element of which
            //       is an index "i" to a "value" array where a string that can be generated by the
            //       nonterminal in question starts. The elements of the string are located in
            //       vcalue[i], value[i+1] ...  until an element value[i+?] == 0 is reached.
            //
            IntArrayList listForNt = stringGenerated.get(nt);
            if (chosenRhs.isEmpty())
                listForNt.add(Util.OMEGA);
            else
                listForNt.addAll(chosenRhs);
        }

        //
        // Note that as long as a parsable string for NT was found, we accept it for and mark
        // NT as complete. Any other string that involves NT in a strongly-connected component
        // cannot be shorter than this string.
        //
        if (successful || indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            for (int symbol = stack.remove(top); symbol != nt; symbol = stack.remove(--top))
                indexOf.set(symbol, Util.OMEGA); // reset index so that symbol can be retried with completed NT later
            indexOf.set(nt, Util.INFINITY);
        }
    }

    //
    // This subroutine computes generates_null(x) for some nonterminal x using the
    // digraph algorithm.
    // generates_null(x) is a boolean indicating whether or not x can generate
    // the empty string.
    //
    private void checkCanGenerateNull(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);
        generatesNull.set(nt, false);

        //
        // A non-terminal A can generate empty iff the grammar in question contains
        // a rule:
        //
        //          A ::= B1 B2 ... Bn     n >= 0,  1 <= i <= n
        //
        // and Bi, for all i, is a nullable non-terminal.
        //
        IntArrayList rules = grammar.rulesOfLhs(nt);
        for (int k = 0, m = rules.size(); k < m && !generatesNull.get(nt); k++)
        {
            int ruleNo = rules.get(k);
            boolean ruleGeneratesEmpty = true; // assume this is true and see if we can prove it!
            for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo) && ruleGeneratesEmpty; i++)
            {
                int symbol = grammar.rhsSym.get(i);
                if (grammar.isNonTerminal(symbol))
                {
                    if (indexOf.get(symbol) == Util.OMEGA)
                        checkCanGenerateNull(symbol);
                    indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));
                    ruleGeneratesEmpty = generatesNull.get(symbol);
                }
                else
                    ruleGeneratesEmpty = false; // terminal indicates that this rule does not generate empty
            }

            generatesNull.set(nt, ruleGeneratesEmpty);
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            for (int symbol = stack.remove(top); symbol != nt; symbol = stack.remove(--top))
            {
                generatesNull.set(symbol, generatesNull.get(nt));
                indexOf.set(symbol, Util.INFINITY);
            }
            indexOf.set(nt, Util.INFINITY);
        }
    }

    //
    // Compute rank for each rule if needed.
    // TODO: This is a temporary algorithm. A much deeper
    // analysis is required...
    //
    private void computeRank(int nt)
    {
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);

        //
        // Iterate over all rules generated by non-terminal NT...
        // In this application of the transitive closure algorithm,
        //
        //  G(A) := { t | A ::= t X for a terminal t and a string X }
        //
        // The relation R is defined as follows:
        //
        //    R(A, Bi) and R(A, B) iff A ::= B1 B2 ... Bk B X
        //
        // where Bi is nullable for 0 <= i <= k and B is not nullable
        //
        IntArrayList listForNt = lhsRankedRules.get(nt);
        for (int k = 0, m = listForNt.size(); k < m; k++)
        {
            int ruleNo = listForNt.get(k);
            for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo); i++)
            {
                int symbol = grammar.rhsSym.get(i);
                if (grammar.isNonTerminal(symbol))
                {
                    if (indexOf.get(symbol) == Util.OMEGA)
                        computeRank(symbol);
                    indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(symbol)));

                    if (!isNullable(symbol))
                        break;
                }
                else
                    break;
            }
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            int symbol = stack.get(top);
            if (nt == symbol)
            {
                processRank(symbol);
                indexOf.set(symbol, Util.INFINITY);
                stack.remove(top);
            }
            else // a non-trivial SCC
            {
                IntArrayList scc = new IntArrayList();
                sccInRanks.add(scc);
                do
                {
                    symbol = stack.remove(top--);
                    scc.add(symbol);
                    processRank(symbol);
                    indexOf.set(symbol, Util.INFINITY);
                }
                while (symbol != nt);
            }
        }
    }

    //
    // Assign a rank to all rules whose left-hand side is "symbol" who
    // were not explicitly prioritized.
    //
    private void processRank(int symbol)
    {
        //
        // List of empty rules associated with symbol.
        // Note that we only consider explicitly specified NULL
        // productions; nullable productions, i.e., a production
        // whose right-hand side consists of a sequence of nullable
        // nonterminals are not considered.
        //
        IntArrayList emptyRules = new IntArrayList();
        IntArrayList nullableRules = new IntArrayList();

        //
        // In this loop, as we iterate over the non-prioritized rules associated
        // with a nonterminal, we assign ranks to them in the order in which they
        // appear unless they happen to be empty or nullable rules in which case
        // we add them to separate respective lists.
        //
        IntArrayList listForSymbol = lhsRankedRules.get(symbol);
        for (int i = 0, n = listForSymbol.size(); i < n; i++)
        {
            int ruleNo = listForSymbol.get(i);
            int firstItem = firstItemOf[ruleNo];
            int firstRhsSymbol = itemTable[firstItem].symbol;
            if (grammar.rhsSize(ruleNo) == 0)
                emptyRules.add(ruleNo);
            else if (grammar.isNonTerminal(firstRhsSymbol) &&
                     isNullable(firstRhsSymbol) &&
                     first(itemTable[firstItem].suffixIndex).get(grammar.empty))
                nullableRules.add(ruleNo);
            else
                orderedRules.add(ruleNo);
        }

        //
        // We now assign ranks to the nullable rules.
        //
        orderedRules.addAll(nullableRules);

        //
        // We now assign ranks to the empty rules.
        //
        orderedRules.addAll(emptyRules);
    }

    //
    //  FIRST_MAP takes as arguments two pointers, ROOT and TAIL, to a sequence
    // of symbols in RHS which it inserts in FIRST_TABLE.  The vector FIRST_TABLE
    // is used as the base for a hashed table where collisions are resolved by
    // links.  Elements added to this hash table are allocated from the vector
    // FIRST, with the variable TOP always indicating the position of the
    // last element in FIRST that was allocated.
    // NOTE: The suffix indentified by ROOT and TAIL is presumed not to be empty.
    //       That is, ROOT <= TAIL !!!
    //
    private int firstMap(int root, int tail)
    {
        FirstElementType firstElem = null;
        for (int i = firstTable[grammar.rhsSym.get(root)]; i != Util.NIL; i = firstElem.link)
        {
            firstElem = first.get(i);
            int j = root + 1;
            int k = firstElem.suffixRoot + 1;
            for (; j <= tail && k <= firstElem.suffixTail; j++, k++)
            {
                if (grammar.rhsSym.get(j) != grammar.rhsSym.get(k))
                    break;
            }
            if (j > tail && k > firstElem.suffixTail)
                return i;
        }

        int index = first.size();
        int link = grammar.rhsSym.get(root);
        first.add(new FirstElementType(root, tail, firstTable[link]));
        firstTable[link] = index;

        return index;
    }

    //
    // SuffixFirst computes the set of all terminals that can appear as the first symbol
    // in a rule suffix  and places the result in the FIRST set indexable by INDEX.
    //
    private void suffixFirst(int index)
    {
        FirstElementType firstElem = first.get(index);
        int root = firstElem.suffixRoot;
        int tail = firstElem.suffixTail;
        int symbol = root > tail ? grammar.empty : grammar.rhsSym.get(root);

        if (grammar.isTerminal(symbol))
        {
            firstElem.set.clear();
            firstElem.set.set(symbol); // add it to set
        }
        else
            firstElem.set = (BitSet)ntFirst.get(symbol).clone();

        for (int i = root + 1; i <= tail && firstElem.set.get(grammar.empty); i++)
        {
            symbol = grammar.rhsSym.get(i);
            firstElem.set.clear(grammar.empty); // remove EMPTY
            if (grammar.isTerminal(symbol))
                firstElem.set.set(symbol); // add it to set
            else
                firstElem.set.or(ntFirst.get(symbol));
        }
    }

    //
    // For a given symbol, complete the computation of
    // PRODUCES[symbol].
    //
    private void computeProduces(int symbol)
    {
        stack.add(symbol);
        int indx = stack.size();
        indexOf.set(symbol, indx);

        IntArrayList listForSymbol = directProduces.get(symbol);
        for (int i = 0, n = listForSymbol.size(); i < n; i++)
        {
            int newSymbol = listForSymbol.get(i);
            if (indexOf.get(newSymbol) == Util.OMEGA)  // first time seen?
                computeProduces(newSymbol);
            indexOf.set(symbol, Math.min(indexOf.get(symbol), indexOf.get(newSymbol)));
            produces.get(symbol).or(produces.get(newSymbol));
        }

        if (indexOf.get(symbol) == indx)  //symbol is SCC root
        {
            int top = stack.size() - 1;
            for (int newSymbol = stack.remove(top); newSymbol != symbol; newSymbol = stack.remove(--top))
            {
                produces.set(newSymbol, (BitSetWithOffset)produces.get(symbol).clone());
                indexOf.set(newSymbol, Util.INFINITY);
            }
            indexOf.set(symbol, Util.INFINITY);
        }
    }

    //
    // COMPUTE_FOLLOW computes FOLLOW[nt] for some non-terminal NT using the
    // digraph algorithm.  FOLLOW[NT] is the set of all terminals Ti that
    // may immediately follow a string X generated by NT. I.e., if NT *::= X
    // then X Ti is a valid substring of a class of strings that may be
    // recognized by the language.
    //
    private void computeFollow(int nt)
    {
        //
        // FOLLOW[NT] was initialized to 0 for all non-terminals.
        //
        stack.add(nt);
        int indx = stack.size();
        indexOf.set(nt, indx);

        //
        // iterate over all items of NT
        //
        for (int itemNo = ntItems.get(nt); itemNo != Util.NIL; itemNo = nextItem[itemNo])
        {
            BitSet tempSet = (BitSet)first.get(itemTable[itemNo].suffixIndex).set.clone();
            if (tempSet.get(grammar.empty))
            {
                tempSet.clear(grammar.empty);
                int ruleNo = itemTable[itemNo].ruleNumber;
                int lhsSymbol = grammar.rules.get(ruleNo).lhs;
                if (indexOf.get(lhsSymbol) == Util.OMEGA)
                    computeFollow(lhsSymbol);
                follow.get(nt).or(follow.get(lhsSymbol));
                indexOf.set(nt, Math.min(indexOf.get(nt), indexOf.get(lhsSymbol)));
            }
            follow.get(nt).or(tempSet);
        }

        if (indexOf.get(nt) == indx)
        {
            int top = stack.size() - 1;
            for (int lhsSymbol = stack.remove(top); lhsSymbol != nt; lhsSymbol = stack.remove(--top))
            {
                follow.set(lhsSymbol, (BitSet)follow.get(nt).clone());
                indexOf.set(lhsSymbol, Util.INFINITY);
            }
            indexOf.set(nt, Util.INFINITY);
        }
    }

    //
    // This procedure is invoked when LALR_LEVEL > 1 to construct the
    // RMPSELF set which identifies the nonterminals that can right-most
    // produce themselves. It takes as argumen the map PRODUCES which
    // identifies for each nonterminal the set of nonterminals that it can
    // right-most produce.
    //
    private void initRmpself(BoundedArray<BitSetWithOffset> produces)
    {
        rmpself = new BoundedBooleanArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());

        //
        // Note that each element of the map produces is a boolean vector
        // that is indexable in the range 1..num_nonterminals. Since each
        // nonterminal is offset by the value numTerminals (to distinguish
        // it from the terminals),it must therefore be adjusted accordingly
        // when dereferencing an element in the range of the produces map.
        //
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            rmpself.set(nt, produces.get(nt).get(nt));
    }

    //
    // Look for duplicate rules and report them.
    //
    private void checkDuplicateRules()
    {
        IntArrayList list = new IntArrayList();
        for (int symbol = grammar.firstNonTerminal(); symbol <= grammar.lastNonTerminal(); symbol++)
        {
            IntArrayList rules = grammar.rulesOfLhs(symbol);
            for (int j = 0, n = rules.size(); j < n; j++)
            {
                int thisRule = rules.get(j); // rule for which we are checking duplication
                for (int k = 0; k < j; k++)
                {
                    int ruleNo = rules.get(k);
                    if (grammar.rhsSize(ruleNo) == grammar.rhsSize(thisRule))
                    {
                        int i1 = grammar.firstRhsIndex(ruleNo);
                        int i2 = grammar.firstRhsIndex(thisRule);
                        for (; i1 < grammar.endRhsIndex(ruleNo); i1++, i2++)
                        {
                            if (grammar.rhsSym.get(i1) != grammar.rhsSym.get(i2))
                                break;
                        }

                        if (i1 == grammar.endRhsIndex(ruleNo))
                        {
                            list.add(thisRule);
                            break; // once we've found a duplicate, no need to keep checking
                        }
                    }
                }
            }
        }

        if (!list.isEmpty())
        {
            for (int i = 0, n = list.size(); i < n; i++)
            {
                int ruleNo = list.get(i);
                int sourceIndex = grammar.rules.get(ruleNo).sourceIndex;
                option.emitError(grammar.parser.rules.get(sourceIndex).separatorIndex,
                                    "This duplicate rule will cause reduce-reduce conflicts");
            }
            control.exit();
        }
    }

    private void printUnreachables()
    {
        //
        // symbolList is used for two purposes:
        //  1) to mark symbols that are reachable from the Accepting
        //        non-terminal.
        //  2) to construct lists of symbols that are not reachable.
        //
        int[] symbolList = new int[grammar.numSymbols + 1];
        Arrays.fill(symbolList, Util.OMEGA);
        symbolList[grammar.eofImage] = Util.NIL;
        symbolList[grammar.empty] = Util.NIL;
        if (option.errorMaps)
            symbolList[grammar.errorImage] = Util.NIL;

        //
        // Initialize a list consisting only of the Accept non-terminal.
        // This list is a work pile of non-terminals to process as follows:
        // Each non-terminal in the front of the list is removed in turn and
        // 1) All terminal symbols in one of its right-hand sides are
        //     marked reachable.
        // 2) All non-terminals in one of its right-hand sides are placed
        //     in the the work pile of it had not been processed previously
        //
        int ntRoot = grammar.acceptImage;
        symbolList[ntRoot] = Util.NIL;
        for (int nt = ntRoot; nt != Util.NIL; nt = ntRoot)
        {
            ntRoot = symbolList[nt];

            IntArrayList rules = grammar.rulesOfLhs(nt);
            for (int k = 0, m = rules.size(); k < m; k++)
            {
                int ruleNo = rules.get(k);
                for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo); i++)
                {
                    int symbol = grammar.rhsSym.get(i);
                    if (grammar.isTerminal(symbol))
                        symbolList[symbol] = Util.NIL;
                    else if (symbolList[symbol] == Util.OMEGA)
                    {
                        symbolList[symbol] = ntRoot;
                        ntRoot = symbol;
                    }
                }
            }
        }

        //
        // We now iterate (backwards to keep things in order) over the
        // terminal symbols, and place each unreachable terminal in a
        // list. If the list is not empty, we signal that these symbols
        // are unused.
        //
        int tRoot = Util.NIL;
        for (int symbol = grammar.lastTerminal(); symbol >= grammar.firstTerminal(); symbol--)
            if (symbolList[symbol] == Util.OMEGA)
            {
                symbolList[symbol] = tRoot;
                tRoot = symbol;
            }

        StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
        for (int symbol = tRoot; symbol != Util.NIL; symbol = symbolList[symbol])
        {
            grammar.restoreSymbol(tok, grammar.retrieveString(symbol));

            option.emitInformative(grammar.retrieveTokenLocation(symbol),
                    "The terminal " + tok + " is useless.");
        }

        //
        // We now iterate (backward to keep things in order) over the
        // non-terminals, and place each unreachable non-terminal in a
        // list.
        //
        ntRoot = Util.NIL;
        for (int symbol = grammar.lastNonTerminal(); symbol >= grammar.firstNonTerminal(); symbol--)
        {
            if (symbolList[symbol] == Util.OMEGA)
            {
                symbolList[symbol] = ntRoot;
                ntRoot = symbol;
            }
        }

        //
        // If the list of unreachable nonterminals is not empty, we signal that
        //  each of these symbols is useless.
        //
        for (int symbol = ntRoot; symbol != Util.NIL; symbol = symbolList[symbol])
        {
            grammar.restoreSymbol(tok, grammar.retrieveString(symbol));

            option.emitWarning(grammar.retrieveTokenLocation(symbol),
                    "The nonterminal " + tok + " is useless.");
        }

    }

    //
    // If output listing was requested, generate it here.
    //
    void processBaseOutput()
    {
        //
        // If a Cross_Reference listing is requested, it is generated
        // here.
        //
        if (option.xref)
        {
            //
            // sortSym is used to sort the symbols for cross_reference listing.
            //
            VariableSymbol[] sortSym = new VariableSymbol[grammar.numSymbols];
            int[] numSymbols = new int[grammar.numTerminals + 1];
            Arrays.fill(numSymbols, Util.NIL);

            for (int ruleNo = grammar.lastRule(); ruleNo >= grammar.firstRule(); ruleNo--)
            {
                int itemNo = firstItemOf[ruleNo];
                for (int i = grammar.firstRhsIndex(ruleNo); i < grammar.endRhsIndex(ruleNo); i++)
                {
                    int symbol = grammar.rhsSym.get(i);
                    if (grammar.isTerminal(symbol))
                    {
                        nextItem[itemNo] = numSymbols[symbol];
                        numSymbols[symbol] = itemNo;
                    }
                    itemNo++;
                }
            }

            //
            // Sort the grammar symbols.
            //
            for (int i = 1; i <= grammar.numSymbols; i++)
                sortSym[i - 1] = grammar.symbolIndex.get(i).symbol;
            Util.sort(sortSym);

            output.printXref(sortSym, numSymbols, nextItem);
        }

        //
        // If a listing of the FIRST map is requested, it is generated
        // here.
        //
        if (option.first)
            output.printNonTerminalFirst(ntFirst);

        //
        // If a listing of the FOLLOW map is requested, it is generated
        // here.
        //
        if (option.follow)
            output.printFollowMap();

        if (!grammar.checkPredecessorSetsFor.isEmpty())
        {
            output.printSymbolMap("Last map", last);
            output.printSymbolMap("Predecessor map", predecessor);
        }
    }

    boolean isNullable(int nt)
    {
        return generatesNull.get(nt);
    }

    BitSet nonterminalFirst(int i)
    {
        return ntFirst.get(i);
    }

    BitSet first(int i)
    {
        return first.get(i).set;
    }

    //
    // CLOSURE is a mapping from non-terminal to a set (linked-list) of
    // non-terminals.  The set consists of non-terminals that are
    // automatically introduced via closure when the original non-terminal
    // is introduced.
    // CL_ITEMS is a mapping from each non-terminal to a set (linked list)
    // of items which are the first item of the rules generated by the
    // non-terminal in question. ADEQUATE_ITEM is a mapping from each rule
    // to the last (complete) item produced by that rule.
    // itemTable is used to map each item into a number. Given that
    // number one can retrieve the rule the item belongs to, the position
    // of the dot,  the symbol following the dot, and FIRST of the suffix
    // following the "dot symbol".
    //
    BoundedArray<IntArrayList> closure = null;
    BoundedArray<IntArrayList> clitems = null;

    Node[] adequateItem = null;

    Itemtab[] itemTable = null;

    int[] rank = null;

    //
    // FOLLOW is a mapping from non-terminals to a set of terminals that
    // may appear immediately after the non-terminal.
    //
    BoundedArray<BitSet> follow = null;

    //
    // RMPSELF is a boolean vector that indicates whether or not a given
    // non-terminal can right-most produce itself. It is only constructed
    // when LALR_LEVEL > 1.
    //
    BoundedBooleanArray rmpself = null;

    //
    // STRING_GENERATED(A) is a map from a nonterminal A into a string in the
    // language that A can generate.
    // PROSTHESIS_RULE(A) is a mapping from A into the rule that
    // was used to generate the string in STRING_GENERATED(A).
    //
    BoundedArray<IntArrayList> stringGenerated = null;
    BoundedIntArray prosthesisRule = null;

    private static final int MAX_LENGTH = Control.PRINT_LINE_SIZE - 4;

    private final IntArrayList stack = new IntArrayList();
    private int[] firstTable = null;
    private int[] firstItemOf = null;
    private int[] nextItem = null;

    private BoundedIntArray indexOf = null;
    private BoundedIntArray ntItems = null;

    private BoundedArray<IntArrayList> lhsRankedRules = null;
    private final List<IntArrayList> sccInRanks = new ArrayList<IntArrayList>();
    private final IntArrayList orderedRules = new IntArrayList();

    //
    // nt_first is a mapping from each nonterminal A into First(A).
    // first is a mapping from all suffix index y derived from an item
    // of the form [A.x.B y], where A and B are nonterminals and
    // x and y ar arbitrary strings, into First(y). Note that each
    // such suffixes has been mapped into a unique integer in "itemtab".
    //
    private BoundedArray<BitSet> ntFirst = null;

    //
    // LAST is a map from each grammar symbol into the set of terminals
    // that may appear last in a string derived from that symbol.
    // PREDECESSOR is a map from each grammar symbol into the set of
    // terminals that may immediately precede the symbol in question.
    //
    private BitSet[] last = null;
    private BitSet[] predecessor = null;
    private IntArrayList[] itemOf = null;

    private final List<FirstElementType> first = new ArrayList<FirstElementType>();

    private BoundedArray<IntArrayList> directProduces = null;
    private BoundedArray<BitSetWithOffset> produces = null;

    //
    // GENERATES_STRING is a boolean vector that indicates whether or not a given
    // non-terminal can generate a string of terminals or the empty string.
    // IS_CYCLIC is a boolean vector that indicates whether or not a given
    // nonterminal is part of a cycle that prevent it from generating a string,
    // possibly empty, of terminals.
    //
    // GENERATES_NULL is a boolean vector that indicates whether or not a given
    // non-terminal is nullable.
    //
    // GENERATES is a map from each nonterminal into a string of terminals it
    // can produce.
    //
    private BoundedBooleanArray generatesString = null;
    private BoundedBooleanArray isCyclic = null;
    private BoundedBooleanArray generatesNull = null;

    private final Control control;
    private final Option option;
    private final LexStream lexStream;
    private final Grammar grammar;

    private final BaseOutput output;

    private static class FirstElementType
    {
        FirstElementType()
        {
            this(0, 0, 0);
        }

        FirstElementType(int suffixRoot, int suffixTail)
        {
            this(suffixRoot, suffixTail, 0);
        }

        FirstElementType(int suffixRoot, int suffixTail, int link)
        {
            this.suffixRoot = suffixRoot;
            this.suffixTail = suffixTail;
            this.link       = link;
        }

        private int suffixRoot;
        private int suffixTail;
        private int link;
        private BitSet set;
    }

    static class Itemtab
    {
        Itemtab(int ruleNumber, int symbol, int dot, int suffixIndex)
        {
            this.ruleNumber = ruleNumber;
            this.symbol = symbol;
            this.dot = dot;
            this.suffixIndex = suffixIndex;
        }

        final int ruleNumber;
        final int symbol;
        final int dot;
              int suffixIndex = Util.NIL;
    }

}
